/**
 * 二进制求和
 *
 * 给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
 *
 * 示例 1：
 * 输入:a = "11", b = "1"
 * 输出："100"
 * 示例 2：
 * 输入：a = "1010", b = "1011"
 * 输出："10101"
 *
 * 提示：
 * 1 <= a.length, b.length <= 104
 * a 和 b 仅由字符 '0' 或 '1' 组成
 * 字符串如果不是 "0" ，就不含前导零
 */

/**
 * 咱从后向前遍历, 用一个进位符标记是否进位
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(n)
 */

public class Main {

    // 测试用例
    public static void main(String[] args) {
        Main test = new Main();
        test.addBinary("11", "1");
    }
    public String addBinary(String a, String b) {

        // 转化为字符数组
        char[] ch1 = a.toCharArray();
        char[] ch2 = b.toCharArray();

        // 定义两个变量指向 ch1 和 ch2 的 最后下标
        int m = ch1.length - 1, n = ch2 .length - 1;

        // 进位标志
        int tmp = 0;

        // 字符串拼接函数
        StringBuffer ret = new StringBuffer();

        // 满足三个条件就可以返回了
        // 1. ch1遍历完
        // 2. ch2 遍历完
        // 3. 不用再向前在进位l
        while (tmp > 0 || m >= 0 || n >= 0) {

            // 定义这个位置的值
            int k = 0;

            if (m >= 0) {
                k += ch1[m] - '0';
                m--;
            }

            if (n >= 0) {
                k += ch2[n] - '0';
                n--;
            }

            // 加上进位
            k += tmp;

            // 更新进位符
            tmp = k / 2;

            // 更新这个位置的值
            k %= 2;

            // 将这个值加入字符串凭借函数
            ret.append(k);
        }

        // 我们因为是倒序插入, 所以在返回的时候要将集合到过来, 并转化为字符串
        return ret.reverse().toString();
    }
}